In an interconnected computer network, the devices communicate through transactions. A transaction comprises one or more packets and conveys some meaningful information. For example, a CPU in a multiprocessor network may respond to a snoop request with a "snoop response" transaction. Generally, a packet consists of a fixed number of transfers or cycles in the interconnect structure. Different transactions may require different number of packets. A transaction may comprise one or more packets forming the header, followed by zero or more packets forming the accompanying data. The header packet(s) may comprise information such as the source node identifier, the destination node identifier, the address bits, the transaction identifier, length of the transaction, flow-control information. Note that different terms are sometimes used but have the same meaning, for example, it is common to use the terms address cycle and data cycle for the header packet and the data packet, respectively.
The raw bandwidth of an interconnect structure is determined by the number of wires and the frequency at which data is transferred. For example, the raw bandwidth available in a 39-bit wide bus, operating at 100 MHz, is 3900 Mbits/sec. The usable bandwidth would be less due to ECC and header packet overheads. The usable bandwidth will depend on the efficiency of the underlying protocol.
The prior art approach to improving the bandwidth relies on expanding the interconnect width and/or increasing the frequency of operation. This approach yields better bandwidth via wider interconnect andp/or faster data transfer. Thus, the improvement in usable bandwidth is solely due to the improvement in the raw bandwidth. The ratio of the usable bandwidth to the raw bandwidth remains unchanged. However, increasing the raw bandwidth is expensive in terms of manufacturing costs. Moreover, the increase in raw bandwidth may lead to electrical problems in the system interconnect interface. Note that technological limitations will restrict the amount with which the raw bandwidth can be increased.
Encoding schemes such as Hoffman encoding may be able to achieve more bandwidth by encoding the most frequently occurring patterns with less number of bits. However, Hoffman encoding require that these bit patterns be known before their actual use, so that the most used bit patterns are assigned the smallest number of bits. For example, assume that a system uses 4 bits in a pattern, and 1111 is the most common pattern. Using Hoffman coding, this pattern will be assigned 0. The next most common pattern will be assigned 10, the next will be assigned 110, then 1110, etc. Thus, Hoffman coding uses variable lengths of bit patterns to indicate the same width of data transfer. Note that some bit patterns are represented by a single bit and others, particularly, the least used patterns will be represented by more than 4 bits.
In typical systems, it is not possible to identify patterns that are more likely to occur than others, because computer systems exhibit a locality of reference that changes over time with regards to addresses and data patterns. Thus, in a computer system one may not be able to predict which addresses are more likely to be accessed than others, since this depends on the application, and space the address patterns change as the program executes. In other words, if a particular page or address is accessed, then most likely a nearby address will be accessed next. Hoffman codes are static and cannot change over time. Moreover, Hoffman encoding requires more bits for the patterns that are "less likely", as a result one may end up in degraded performance.
Therefore, there is a need in the art for a mechanism which will improve the ratio of usable bandwidth to the raw bandwidth and thereby increase the bandwidth without having to increase the frequency or the number of wires.